package structure;
import java.util.*;

public class Test4 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

    }
    //leetcode 61.旋转链表
    class Solution {
        public ListNode rotateRight(ListNode head, int k) {
            if(head == null || head.next == null || k == 0){
                return head;
            }
            ListNode cur = head;
            int len = 1;
            while(cur.next != null){
                cur = cur.next;
                len++;
            }
            int add = len - k % len;
            if(len == add){
                return head;
            }
            cur.next = head;
            while(add-- > 0){
                cur = cur.next;
            }
            ListNode Head = cur.next;
            cur.next = null;
            return Head;
        }
    }
    //leetcode 148.排序链表
    class Solution {
        public ListNode sortList(ListNode head) {
            if (head == null || head.next == null) {
                return head;
            }
            // 找到中间节点
            ListNode mid = getMid(head);
            ListNode right = mid.next;
            mid.next = null;
            // 递归排序左右子链表
            ListNode left = sortList(head);
            right = sortList(right);
            // 合并两个有序链表
            return merge(left, right);
        }

        private ListNode getMid(ListNode head) {
            ListNode slow = head;
            ListNode fast = head.next;
            while (fast!= null && fast.next!= null) {
                slow = slow.next;
                fast = fast.next.next;
            }
            return slow;
        }

        private ListNode merge(ListNode cur1, ListNode cur2) {
            ListNode Head = new ListNode();
            ListNode pHead = Head;
            while (cur1!= null && cur2!= null) {
                if (cur1.val < cur2.val) {
                    Head.next = cur1;
                    cur1 = cur1.next;
                } else {
                    Head.next = cur2;
                    cur2 = cur2.next;
                }
                Head = Head.next;
            }
            if (cur1!= null) {
                Head.next = cur1;
            } else {
                Head.next = cur2;
            }
            return pHead.next;
        }
    }
}

